package leetcode.剑指offer.剑指II;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/9/25 15:17
 * @description：
 */
public class 剑指_II_007_数组中和为0的三个数 {

    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.threeSum(new int[]{-1,0,1,2,-1,-4}));
    }

    class Solution {
        List<List<Integer>> ans;
        Set<ArrayList<Integer>> set;
        int[] nums;
        public List<List<Integer>> threeSum(int[] nums) {
            this.nums = nums;
            set = new HashSet<>();
            ans = new ArrayList<>();
            if (nums.length < 3) return ans;
            dfs(0, new ArrayList<>(), 0);
            ans.sort((o1, o2) -> {
                if (o1.get(0).compareTo(o2.get(0)) != 0) {
                    return o1.get(0).compareTo(o2.get(0));
                } else if (o1.get(1).compareTo(o2.get(1)) != 0) {
                    return o1.get(1).compareTo(o2.get(1));
                } else
                    return o1.get(2).compareTo(o2.get(2));
            });
            return ans;
        }

        private void dfs(int index, ArrayList<Integer> pre, int curSum) {
            if (pre.size() == 3) {
                if (curSum == 0) {
                    ArrayList<Integer> sub = new ArrayList<>(pre);
                    sub.sort(Integer::compareTo);
                    if (set.add(sub))
                        ans.add(sub);
                }
                return;
            }
            for (int i = index; i < nums.length; i++) {
                ArrayList<Integer> cur = new ArrayList<>(pre);
                cur.add(nums[i]);
                dfs(i + 1, cur, curSum + nums[i]);
            }
        }
    }

}
